//挖地雷 此法为图的多源最短路径floyd的变式，通用所有情形
//如果规定一条边（u,v) 的起点小于终点（u<v），则可以简单地按点的反向顺序进行动态规划
#include <iostream>
using namespace std;
const int MAXN=200;
int n;
int w[MAXN+1];
bool adj[MAXN+1][MAXN+1];
int maxw[MAXN+1][MAXN+1];
int select[MAXN+1][MAXN+1];
void output(int x,int y){
    int mid=select[x][y];
    if (mid>0){
        output(x,mid);
        output(mid,y);
    }else {
        cout<<x<<'-';
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    int x,y;
    do{
        cin>>x>>y;
        if (x>0){
            adj[x][y]=true;
        }else break;
    }while(1);
    //floyd算法
    for(int x=1;x<=n;x++)
        for(int y=1;y<=n;y++){
            if (x==y) maxw[x][y]=w[x];
            else if (adj[x][y]) maxw[x][y]=w[x]+w[y];
        }
     for(int mid=1;mid<=n;mid++) 
        for(int x=1;x<=n;x++)
            for(int y=1;y<=n;y++)
                if (mid!=x&&x!=y&&y!=mid)
                    if (maxw[x][mid]>0&&maxw[mid][y]>0&&(maxw[x][mid]+maxw[mid][y]-w[mid]>maxw[x][y])){
                        maxw[x][y]=maxw[x][mid]+maxw[mid][y]-w[mid];
                        select[x][y]=mid;
                    }
    //找出最大者
    int ans=0,ans_x,ans_y;
    for(int x=1;x<=n;x++)
        for(int y=1;y<=n;y++)
            if (maxw[x][y]>ans) {
                ans=maxw[x][y];
                ans_x=x;
                ans_y=y;
            }
    //输出结果
    if (ans_x==ans_y) cout<<ans_x<<endl;
    else {
        output(ans_x,ans_y);
        cout<<ans_y<<endl;
    }
    cout<<ans<<endl;
} 
